package com.explorati.LeetCode209.minimumsizesubarraysum;

/**
 * 209. Minimum Size Subarray Sum
 * 
 * Given an array of n positive integers and a positive integer s, find the
 * minimal length of a contiguous subarray of which the sum ≥ s. If there isn't
 * one, return 0 instead.
 * 
 * Input: s = 7, nums = [2,3,1,2,4,3] Output: 2 Explanation: the subarray [4,3]
 * has the minimal length under the problem constraint.
 * 
 * @author explorati
 *
 */
// 时间复杂度O(n)
// 空间复杂度O(1)
public class Solution {
	public static int minSubArrayLen(int s, int[] nums) {
		int res = nums.length + 1, temp = 0;
		int l = 0, r = -1;
		int sum = 0;
		while (l != nums.length) {
			if (sum < s && r < nums.length - 1) {
				sum += nums[++r];
			} else {
				sum -= nums[l++];
			}
			if (sum >= s) {
				temp = r - l + 1;
				if (temp < res) {
					res = temp;
				}
			}
		}
		if (res == nums.length + 1) {
			return 0;
		}
		return res;
	}

	public static void main(String[] args) {
		int[] arr = { 5, 1, 3, 5, 10, 7, 4, 9, 2, 8 };
		System.out.println(minSubArrayLen(15, arr));
	}
}
